package 中等.前后缀分解;

/**
 * 给你一个下标从 0 开始的整数数组 nums 。
 * 请你从所有满足 i < j < k 的下标三元组 (i, j, k) 中，找出并返回
 * 下标三元组的最大值。如果所有满足条件的三元组的值都是负数，则返回 0 。
 * 下标三元组 (i, j, k) 的值等于 (nums[i] - nums[j]) * nums[k] 。
 *
 * @ https://leetcode.cn/problems/maximum-value-of-an-ordered-triplet-ii/description/
 * @date 2024/07/24
 */
public class 有序三元组中的最大值II_2874 {

    public static void main(String[] args) {

        System.out.println(maximumTripletValue(new int[]{8, 6, 3, 13, 2, 12, 19, 5, 19, 6, 10, 11, 9}));

    }

    /**
     * 对于中间的元素 j ，需要找到 [0,j-1] 的最大元素 和 [j+1,n-1] 的最大元素
     * 就是这个三元组的最大值
     */
    public static long maximumTripletValue(int[] nums) {
        long ans = 0;
        int[] suffixMax = new int[nums.length];

        suffixMax[nums.length - 1] = nums[nums.length - 1];
        for (int i = suffixMax.length - 2; i >= 0; i--) {
            suffixMax[i] = Math.max(nums[i], suffixMax[i + 1]);
        }

        int[] prefixMax = new int[nums.length];
        prefixMax[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            prefixMax[i] = Math.max(prefixMax[i - 1], nums[i]);
        }

        for (int j = 1; j < nums.length - 1; j++) {
            ans = Math.max(ans, (prefixMax[j - 1] - nums[j]) * (long) suffixMax[j + 1]);
        }

        return ans;
    }

}
